/*# 写代码的注意事项

以下，是我们课上发现的程序问题，大家都要记住，不要再犯同样的错误：

## 代码中使用的 `{}` 格式要统一

可以是这样：

```c++
int fn() {

}
```

也可以是这样：

```c++
int fn()
{

}
```

选择一种自己喜欢的，然后在整个代码里，保持一致，不要混用。

## 正确使用 vector 的迭代器

对于 `vector<int> v` 来说，为了访问它的第一个元素，我们可以这样：

```c++
v[0]
```

也可以这样：

```c++
*v.begin();
```

但我们不能把 `begin` 放在 `[]` 里：

```c++
v[v.begin()] // !!! 这是错误的用法
```

# 课外知识补充

## 认识 C++ 指针

**指针**，就像它的名字一样，用于指向程序中的某个位置。来看下面的例子：

```c++
int a = 10;

// 在下面的代码中，我们用 `int *` 让变量 `ptr` 指向程序中某个整数变量的位置。
// 那么这个位置是什么呢？我们用 `&a` 的形式，表示让 `ptr` 指向变量 `a` 的位置。
int *ptr = &a; &a(0x53567890)

// 这样，我们就可以用 `ptr` 间接修改 `a` 了。
*ptr = 11;
// 上面的语句执行完后，现在变量 `a` 的值就是 11 了。

// 接下来，我们还可以让 `ptr` 指向其它变量，例如：
int b = 100;
ptr = &b; // <- 注意，这里使用了 &b

// 现在，我们就可以使用 `ptr` 修改变量 `b` 了。
*ptr = 110;
// 上面的语句执行完后，现在变量 `b` 的值就是 110 了。
```

## 认识 C++ 引用

**引用**，就像它的名字一样，用于引用程序中的某个变量。来看下面的例子：

```c++
int a = 10;

// 在下面的代码中，我们用 `int &` 让变量 `ref` 引用程序中的某个变量。
// 那么具体引用哪个变量呢？我们直接给 `ref` 赋值，表示让 `ref` 引用变量 `a`。
int &ref = a; 

// 这样，我们就可以用 `ref` 间接修改 `a` 了。
ref = 11;
// 上面的语句执行完后，现在变量 `a` 的值就是 11 了。

// 是不是和刚才说的指针有点儿像？
// 但是要注意的是，我们不能让 `ref` 重新引用别的变量
// 但是要注意的是，我们不能让 `ref` 重新引用别的变量
// 但是要注意的是，我们不能让 `ref` 重新引用别的变量

int b = 100;
ref = b; // <- 注意，这条语句是错的，`ref` 已经引用了 `a`，它不能再引用 `b` 了。
```

# 编程题

 提示：**基于动态编程的编程思想，解决下面这个“找零钱”的问题**。

 给定一个数组 `coins`，表示持有的硬币面额（每一种面额的硬币个数不限）。以及一个数字 `n`，表示要找的零钱。编写一个函数，计算使用 `coins` 找钱找出 `n`，所需要的**最小的硬币个数**。
adaaaaaaaaaaaddddddd

 ### 例子

 假设 `coins` 等于 `[1, 5, 10]`。`n` 等于 `7`，那么这个函数应该返回 `3`，也就是使用 2 个面额是 1 的硬币，以及 1 个 面额是 5 的硬币。

 ### 解题*/

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;        

int numberOfWaysToMakeChange(vector<int> coins, int n)
{
    // 创建一个包含 n+1 的元素的数组 ways，表达找从 0 至 n 钱的方法。
    // 并且将ways中每个元素初始化为0
    vector<int> ways(n + 1, 0);

    // ++++++中心思想++++++
    // 要计算n相对于面额k的找钱方法，只需计算n-k的相对于面额k的方法数，以此类推
    // 理解当面额k为面额数组k[k1,k2,...kn]时，那么计算n相对于面额数组k的找钱方法，只需计算n-k的相对于面额数组k的方法数，以此类推
    // ++++++中心思想++++++

    // 遍历所有的面额
    // 对于每一种面额，我们用它去遍历所有要找的钱数
    // 如果能找
    //    更新对应找钱上的方法数 ways[b(找钱)] + ways[b(找钱) - a(面额)]
    // 否则
    //    PASS
    // 所有面额遍历结束，ways 最后一个元素的值，就是答案

    //初始化ways[0]为0，表示找钱0即找开了，记1次
    ways[0] = 0;

    //循环每一种面额
    for (int j = 0; j < coins.size(); j++)
    {
        //循环计算1到n中所有数的相对于一种面额的找钱情况
        for (int i = 1; i <= n; i++)
        {
            //如果面额小于要找开的钱数
            if (coins[j] <= i)
            {
                //把要找钱i的方法数和i-coins[j]的找钱方法数+1做比较，小的存起来
                if(ways[i] == 0 || 1 + ways[i - coins[j]] < ways[i])
                    ways[i] = 1 + ways[i - coins[j]];
            }
                
        }
        //打印每一种面额计算完成后ways中的值
        for (int k = 0; k < ways.size(); k++)
        {
            cout << k << "=" << ways[k] << endl;
        }

        //打印“--”用作分隔，便于查看ways中间值
        cout << "----------------------------------------" << endl;

    }
    
    //返回ways中最后一个元素的值，即是我们要计算要找钱n的方法数
    return (*(ways.end() - 1));
}

int main(int argc, char const *argv[])
{
    //定
    义一个整型变量n 
    int n;
    
    //在屏幕上打印put in
    cout << "put in:";

    //将屏幕上的输入数字保持在变量n里
    cin >> n;

    //定义一个整型数组变量coins，数组里初始化1，5，10，25 四个数字，表示4种面额
    vector<int> coins = {1, 5, 2};
    
    //打印出整型数组变量coins里的所有值，用空格分隔
    for (int i = 0; i < coins.size(); i++)
    {
        cout << coins[i] << " ";
    }
    
    //打印一个换行符
    cout << endl;

    //定义一个整型变量res，同时调用函数numberOfWaysToMakeChange，把
    //numberOfWaysToMakeChange的返回值，初始化赋值给res
    int res = numberOfWaysToMakeChange(coins, n);

    //在屏幕上打印“result:”和res的值
    cout << "result: " << res << endl;

    //main函数返回，返回值为0
    return 0;                              
}